package 链表.反转链表;

import java.util.ArrayList;
import java.util.List;
/**
 * 给你单链表的头节点 head ，请你反转链表，
 * 并返回反转后的链表。
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 力扣地址：https://leetcode-cn.com/problems/reverse-linked-list/
 * 206题
 * */
/**
 * 解题思路
 * 1，题目要求反转链表，那么就是将链表节点的next指针指向前一个节点
 * 2，用List先存储链表节点
 * 3，从原头节点开始，将节点的next指针指向前一个节点
 * 4，最后把原头节点也就是新的尾节点的next指针改为null，避免造成破坏
 * */
/**
 * 举例
 * 步骤 1：把所有节点存入 List
 * 遍历原链表时，会把每个节点按顺序加入 List，所以 list 中的元素是：list = [节点1, 节点2, 节点3, 节点4]（节点 1 是原链表的头，节点 4 是原链表的尾）
 * 步骤 2：确定新的头节点
 * 原链表反转后，原尾节点会变成新的头节点。因为 list 中最后一个元素是原尾节点（节点 4），所以：newHead = list.get(3)（因为 n=4，n-1=3），即 newHead 是节点 4。
 * 步骤 3：核心循环 —— 反转节点的 next 指向
 * 循环的作用是：让每个节点的 next 指针，指向原链表中它前面的那个节点。
 * 原链表中节点的 next 指向是：节点1.next = 节点2节点2.next = 节点3节点3.next = 节点4节点4.next = null
 * 反转后需要变成：节点4.next = 节点3节点3.next = 节点2节点2.next = 节点1节点1.next = null
 * 循环细节（for 循环 i从n-2递减到0）：
 * n=4，所以 i 从 2 开始（n-2=2），依次递减到 0，共 3 次循环。
 * 第一次循环（i=2）：i+1 = 3，所以 list.get(i+1) 是节点 4，list.get(i) 是节点 3。执行 list.get(i+1).next = list.get(i) → 节点 4.next = 节点 3。此时节点 4 的指向变成：4 -> 3。
 * 第二次循环（i=1）：i+1 = 2，所以 list.get(i+1) 是节点 3，list.get(i) 是节点 2。执行 list.get(i+1).next = list.get(i) → 节点 3.next = 节点 2。此时节点 3 的指向变成：3 -> 2（结合上一步，现在是 4->3->2）。
 * 第三次循环（i=0）：i+1 = 1，所以 list.get(i+1) 是节点 2，list.get(i) 是节点 1。执行 list.get(i+1).next = list.get(i) → 节点 2.next = 节点 1。此时节点 2 的指向变成：2 -> 1（现在完整链条是 4->3->2->1）。
 * 步骤 4：处理尾节点（原头节点）
 * 原链表的头节点是 节点1，它原来的 next 是 节点2。反转后 节点1 变成了尾节点，尾节点的 next 必须是 null（否则会形成环：1->2->1...）。
 * 所以执行 list.get(0).next = null → 节点 1.next = null。
 * */

class Solution {
    public ListNode reverseList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        // 节点存入list
        while(head != null){
            list.add(head);
            head = head.next;
        }
        // 处理空链表
        if(list.isEmpty()){
            return null;
        }
        // 设置节点next的走向
        int n = list.size();
        // 原链表的尾节点作为新的头结点
        ListNode newHead = list.get(n - 1);
        // 只所以是n-2是因为，上面已经将n-1设置为新的头结点了，从下一个遍历就可以了
        for(int i = n-2;i >= 0; i--){
            list.get(i + 1).next = list.get(i);
        }
        // 处理原头结点，将原头结点改为新的尾节点
        list.get(0).next = null;
        return newHead;
    }
}